/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：不同路径</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/unique-paths/
 * </pre>
 * <p>创建日期：2019年11月22日下午2:53:49</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code62UniquePaths</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code62UniquePaths
{
	public static void main(String[] args)
	{
		/**
		 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

		机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

		问总共有多少条不同的路径？
		说明：m 和 n 的值均不超过 100。

		示例 1:

		输入: m = 3, n = 2
		输出: 3
		解释:
		从左上角开始，总共有 3 条路径可以到达右下角。
		1. 向右 -> 向右 -> 向下
		2. 向右 -> 向下 -> 向右
		3. 向下 -> 向右 -> 向右
		示例 2:

		输入: m = 7, n = 3
		输出: 28
		 */
		int uniquePaths = uniquePaths(7, 3);
		System.out.println(uniquePaths);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		将整个mXn的网格看成一个二维数组
	 * 		指定dp[i][j]为走到坐标(i,j)位置的路径数
	 * 		则：
	 * 			dp[i][j]=dp[i-1][j]+dp[i][j-1] : 即走到坐标[i,j]的上一步的所有路径数和
	 * 		考虑各种情况：
	 * 			dp[i][j]:{
	 * 						1	:m=0/n=0
	 * 						dp[0][j]=1,dp[i][0]=1 :即只有一条路走到黑
	 * 						dp[i][j]=dp[i-1][j]+dp[i][j-1]
	 * 					}
	 * 
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(n^2)
	 * 
	 * @param m
	 * @param n
	 * @return
	 */
	public static int uniquePaths(int m, int n)
	{
		if (m == 0 || n == 0)
		{
			return 1;
		}
		int[][] dp = new int[m][n];
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				//即一条路走到黑的情况，则每个节点的路径数都是1
				if (i == 0 || j == 0)
				{
					dp[i][j] = 1;
					continue;
				}
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				System.out.print(dp[i][j] + "\t");
			}
			System.out.println("");
		}
		System.out.println("dp[m-1][n-1]:" + dp[m - 1][n - 1]);
		/**
		 * dp[i][j] = dp[i-1][j]+dp[i][j-1]
		 */
		return 0;
	}
}
